home *** CD-ROM | disk | FTP | other *** search
/ EnigmA Amiga Run 1996 June / EnigmA AMIGA RUN 08 (1996)(G.R. Edizioni)(IT)[!][issue 1996-06][EARSAN CD VII].iso / earcd / gcc / ixemlsrc.lha / ixemul / ixnet / split.c < prev    next >
C/C++ Source or Header  |  1996-03-13  |  19KB  |  695 lines
  1. /*-
  2.  * Copyright (c) 1990 The Regents of the University of California.
  3.  * All rights reserved.
  4.  *
  5.  * This code is derived from software contributed to Berkeley by
  6.  * Mike Olson.
  7.  *
  8.  * Redistribution and use in source and binary forms, with or without
  9.  * modification, are permitted provided that the following conditions
  10.  * are met:
  11.  * 1. Redistributions of source code must retain the above copyright
  12.  *    notice, this list of conditions and the following disclaimer.
  13.  * 2. Redistributions in binary form must reproduce the above copyright
  14.  *    notice, this list of conditions and the following disclaimer in the
  15.  *    documentation and/or other materials provided with the distribution.
  16.  * 3. All advertising materials mentioning features or use of this software
  17.  *    must display the following acknowledgement:
  18.  *    This product includes software developed by the University of
  19.  *    California, Berkeley and its contributors.
  20.  * 4. Neither the name of the University nor the names of its contributors
  21.  *    may be used to endorse or promote products derived from this software
  22.  *    without specific prior written permission.
  23.  *
  24.  * THIS SOFTWARE IS PROVIDED BY THE REGENTS AND CONTRIBUTORS ``AS IS'' AND
  25.  * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
  26.  * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
  27.  * ARE DISCLAIMED.  IN NO EVENT SHALL THE REGENTS OR CONTRIBUTORS BE LIABLE
  28.  * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
  29.  * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS
  30.  * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
  31.  * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
  32.  * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY
  33.  * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
  34.  * SUCH DAMAGE.
  35.  */
  36.  
  37. #if defined(LIBC_SCCS) && !defined(lint)
  38. static char sccsid[] = "@(#)split.c     5.2 (Berkeley) 2/22/91";
  39. #endif /* LIBC_SCCS and not lint */
  40.  
  41. #include <sys/types.h>
  42. #include <db.h>
  43. #include <stdlib.h>
  44. #include <string.h>
  45. #include "btree.h"
  46. #include "utils.h"
  47.  
  48. int _bt_dopsplit(BTREE_P, BTHEADER *, BTHEADER *);
  49.  
  50. /*
  51.  *  _BT_SPLIT -- Split a page into two pages.
  52.  *
  53.  *    Splits are caused by insertions, and propogate up the tree in
  54.  *    the usual way.    The root page is always page 1 in the file on
  55.  *    disk, so root splits are handled specially.  On entry to this
  56.  *    routine, t->bt_curpage is the page to be split.
  57.  *
  58.  *    Parameters:
  59.  *        t -- btree in which to do split.
  60.  *
  61.  *    Returns:
  62.  *        RET_SUCCESS, RET_ERROR.
  63.  *
  64.  *    Side Effects:
  65.  *        Changes the notion of the current page.
  66.  */
  67.  
  68. int
  69. _bt_split(t)
  70.     BTREE_P t;
  71. {
  72.     BTHEADER *h;
  73.     BTHEADER *left, *right;
  74.     pgno_t nextpgno, parent;
  75.     int nbytes, len;
  76.     IDATUM *id;
  77.     DATUM *d;
  78.     char *src;
  79.     IDATUM *new;
  80.     pgno_t oldchain;
  81.     u_char flags;
  82.  
  83.     h = (BTHEADER *) t->bt_curpage;
  84.  
  85.     /* split root page specially, since it must remain page 1 */
  86.     if (h->h_pgno == P_ROOT) {
  87.         return (_bt_splitroot(t));
  88.     }
  89.  
  90.     /*
  91.      *  This is a little complicated.  We go to some trouble to
  92.      *  figure out which of the three possible cases -- in-memory tree,
  93.      *  disk tree (no cache), and disk tree (cache) -- we have, in order
  94.      *  to avoid unnecessary copying.  If we have a disk cache, then we
  95.      *  have to do some extra copying, though, since the cache code
  96.      *  manages buffers externally to this code.
  97.      */
  98.  
  99.     if (IS_A_DISK(t) && ISCACHE(t)) {
  100.         if ((left = (BTHEADER *) malloc((unsigned) t->bt_psize))
  101.             == (BTHEADER *) NULL)
  102.             return (RET_ERROR);
  103.         left->h_pgno = left->h_prevpg = left->h_nextpg = P_NONE;
  104.         left->h_flags = t->bt_curpage->h_flags;
  105.         left->h_lower = (index_t)
  106.               (((char *) &(left->h_linp[0])) - ((char *) left));
  107.         left->h_upper = t->bt_psize;
  108.  
  109.     } else {
  110.         if ((left = _bt_allocpg(t)) == (BTHEADER *) NULL)
  111.             return (RET_ERROR);
  112.     }
  113.     left->h_pgno = h->h_pgno;
  114.  
  115.     if ((right = _bt_allocpg(t)) == (BTHEADER *) NULL)
  116.         return (RET_ERROR);
  117.     right->h_pgno = ++(t->bt_npages);
  118.  
  119.     /* now do the split */
  120.     if (_bt_dopsplit(t, left, right) == RET_ERROR)
  121.         return (RET_ERROR);
  122.  
  123.     right->h_prevpg = left->h_pgno;
  124.     nextpgno = right->h_nextpg = h->h_nextpg;
  125.     left->h_nextpg = right->h_pgno;
  126.     left->h_prevpg = h->h_prevpg;
  127.  
  128.     /* okay, now use the left half of the page as the new page */
  129.     if (IS_A_DISK(t) && ISCACHE(t)) {
  130.         (void) bcopy((char *) left, (char *) t->bt_curpage,
  131.                  (int) t->bt_psize);
  132.         (void) free ((char *) left);
  133.         left = t->bt_curpage;
  134.     } else {
  135.         (void) free((char *) t->bt_curpage);
  136.         t->bt_curpage = left;
  137.     }
  138.  
  139.     /*
  140.      *  Write the new pages out.  We need them to stay where they are
  141.      *  until we're done updating the parent pages.
  142.      */
  143.  
  144.     if (_bt_write(t, left, NORELEASE) == RET_ERROR)
  145.         return (RET_ERROR);
  146.     if (_bt_write(t, right, NORELEASE) == RET_ERROR)
  147.         return (RET_ERROR);
  148.  
  149.     /* update 'prev' pointer of old neighbor of left */
  150.     if (nextpgno != P_NONE) {
  151.         if (_bt_getpage(t, nextpgno) == RET_ERROR)
  152.             return (RET_ERROR);
  153.         h = t->bt_curpage;
  154.         h->h_prevpg = right->h_pgno;
  155.         h->h_flags |= F_DIRTY;
  156.     }
  157.  
  158.     if ((parent = _bt_pop(t)) != P_NONE) {
  159.         if (right->h_flags & F_LEAF) {
  160.             d = (DATUM *) GETDATUM(right, 0);
  161.             len = d->d_ksize;
  162.             if (d->d_flags & D_BIGKEY) {
  163.                 bcopy(&(d->d_bytes[0]),
  164.                       (char *) &oldchain,
  165.                       sizeof(oldchain));
  166.                 if (_bt_markchain(t, oldchain) == RET_ERROR)
  167.                     return (RET_ERROR);
  168.                 src = (char *) &oldchain;
  169.                 flags = D_BIGKEY;
  170.             } else {
  171.                 src = (char *) &(d->d_bytes[0]);
  172.                 flags = 0;
  173.             }
  174.         } else {
  175.             id = (IDATUM *) GETDATUM(right, 0);
  176.             len = id->i_size;
  177.             flags = id->i_flags;
  178.             src = (char *) &(id->i_bytes[0]);
  179.         }
  180.         nbytes = len + (sizeof(IDATUM) - sizeof(char));
  181.         new = (IDATUM *) malloc((unsigned) nbytes);
  182.         if (new == (IDATUM *) NULL)
  183.             return (RET_ERROR);
  184.         new->i_size = len;
  185.         new->i_pgno = right->h_pgno;
  186.         new->i_flags = flags;
  187.         if (len > 0)
  188.             (void) bcopy(src, (char *) &(new->i_bytes[0]), len);
  189.  
  190.         nbytes = LONGALIGN(nbytes) + sizeof(index_t);
  191.         if (_bt_getpage(t, parent) == RET_ERROR)
  192.             return (RET_ERROR);
  193.  
  194.         h = t->bt_curpage;
  195.  
  196.         /*
  197.          *  Split the parent if we need to, then reposition the
  198.          *  tree's current page pointer for the new datum.
  199.          */
  200.         if ((h->h_upper - h->h_lower) < nbytes) {
  201.             if (_bt_split(t) == RET_ERROR)
  202.                 return (RET_ERROR);
  203.             if (_bt_reposition(t, new, parent, right->h_prevpg)
  204.                   == RET_ERROR)
  205.                 return (RET_ERROR);
  206.         }
  207.  
  208.         /* okay, now insert the new idatum */
  209.         if (_bt_inserti(t, new, right->h_prevpg) == RET_ERROR)
  210.             return (RET_ERROR);
  211.     }
  212.  
  213.     /*
  214.      *  Okay, split is done; don't need right page stapled down anymore.
  215.      *  The page we call 'left' above is the new version of the old
  216.      *  (split) page, so we can't release it.
  217.      */
  218.  
  219.     if (_bt_release(t, right) == RET_ERROR)
  220.         return (RET_ERROR);
  221.     if (IS_A_DISK(t) && !ISCACHE(t))
  222.         (void) free((char *) right);
  223.  
  224.     return (RET_SUCCESS);
  225. }
  226.  
  227. /*
  228.  *  _BT_REPOSITION -- Reposition the current page pointer of a btree.
  229.  *
  230.  *    After splitting a node in the tree in order to make room for
  231.  *    an insertion, we need to figure out which page after the split
  232.  *    should get the item we want to insert.    This routine positions
  233.  *    the tree's current page pointer appropriately.
  234.  *
  235.  *    Parameters:
  236.  *        t -- tree to position
  237.  *        new -- the item we want to insert
  238.  *        parent -- parent of the node that we just split
  239.  *        prev -- page number of item directly to the left of
  240.  *            new's position in the tree.
  241.  *
  242.  *    Returns:
  243.  *        RET_SUCCESS, RET_ERROR.
  244.  *
  245.  *    Side Effects:
  246.  *        None.
  247.  */
  248.  
  249. int
  250. _bt_reposition(t, new, parent, prev)
  251.     BTREE_P t;
  252.     IDATUM *new;
  253.     pgno_t parent;
  254.     pgno_t prev;
  255. {
  256.     index_t i, next;
  257.     IDATUM *idx;
  258.  
  259.     if (parent == P_ROOT) {
  260.  
  261.         /*
  262.          *  If we just split the root page, then there are guaranteed
  263.          *  to be exactly two IDATUMs on it.  Look at both of them
  264.          *  to see if they point to the page that we want.
  265.          */
  266.  
  267.         if (_bt_getpage(t, parent) == RET_ERROR)
  268.             return (RET_ERROR);
  269.  
  270.         next = NEXTINDEX(t->bt_curpage);
  271.         for (i = 0; i < next; i++) {
  272.             idx = (IDATUM *) GETDATUM(t->bt_curpage, i);
  273.             if (_bt_getpage(t, idx->i_pgno) == RET_ERROR)
  274.                 return (RET_ERROR);
  275.             if (_bt_isonpage(t, new, prev) == RET_SUCCESS)
  276.                 return (RET_SUCCESS);
  277.             if (_bt_getpage(t, parent) == RET_ERROR)
  278.                 return (RET_ERROR);
  279.         }
  280.     } else {
  281.  
  282.         /*
  283.          *  Get the parent page -- which is where the new item would
  284.          *  have gone -- and figure out whether the new item now goes
  285.          *  on the parent, or the page immediately to the right of
  286.          *  the parent.
  287.          */
  288.  
  289.         if (_bt_getpage(t, parent) == RET_ERROR)
  290.             return (RET_ERROR);
  291.         if (_bt_isonpage(t, new, prev) == RET_SUCCESS)
  292.             return (RET_SUCCESS);
  293.         if (_bt_getpage(t, t->bt_curpage->h_nextpg) == RET_ERROR)
  294.             return (RET_ERROR);
  295.         if (_bt_isonpage(t, new, prev) == RET_SUCCESS)
  296.             return (RET_SUCCESS);
  297.     }
  298.     return (RET_ERROR);
  299. }
  300.  
  301. /*
  302.  *  _BT_ISONPAGE -- Is the IDATUM for a given page number on the current page?
  303.  *
  304.  *    This routine is used by _bt_reposition to decide whether the current
  305.  *    page is the correct one on which to insert a new item.
  306.  *
  307.  *    Parameters:
  308.  *        t -- tree to check
  309.  *        new -- the item that will be inserted (used for binary search)
  310.  *        prev -- page number of page whose IDATUM is immediately to
  311.  *            the left of new's position in the tree.
  312.  *
  313.  *    Returns:
  314.  *        RET_SUCCESS, RET_ERROR (corresponding to TRUE, FALSE).
  315.  */
  316.  
  317. int
  318. _bt_isonpage(t, new, prev)
  319.     BTREE_P t;
  320.     IDATUM *new;
  321.     pgno_t prev;
  322. {
  323.     BTHEADER *h = (BTHEADER *) t->bt_curpage;
  324.     index_t i, next;
  325.     IDATUM *idx;
  326.  
  327.     i = _bt_binsrch(t, &(new->i_bytes[0]));
  328.     while (i != 0 && _bt_cmp(t, &(new->i_bytes[0]), i) == 0)
  329.         --i;
  330.     next = NEXTINDEX(h);
  331.     idx = (IDATUM *) GETDATUM(h, i);
  332.     while (i < next && idx->i_pgno != prev) {
  333.         i++;
  334.         idx = (IDATUM *) GETDATUM(h, i);
  335.     }
  336.     if (idx->i_pgno == prev)
  337.         return (RET_SUCCESS);
  338.     else
  339.         return (RET_ERROR);
  340. }
  341.  
  342. /*
  343.  *  _BT_SPLITROOT -- Split the root of a btree.
  344.  *
  345.  *    The root page for a btree is always page one.  This means that in
  346.  *    order to split the root, we need to do extra work.
  347.  *
  348.  *    Parameters:
  349.  *        t -- tree to split
  350.  *
  351.  *    Returns:
  352.  *        RET_SUCCESS, RET_ERROR.
  353.  *
  354.  *    Side Effects:
  355.  *        Splits root upward in the usual way, adding two new pages
  356.  *        to the tree (rather than just one, as in usual splits).
  357.  */
  358.  
  359. int
  360. _bt_splitroot(t)
  361.     BTREE_P t;
  362. {
  363.     BTHEADER *h = t->bt_curpage;
  364.     BTHEADER *left, *right;
  365.     IDATUM *id;
  366.     BTHEADER *where_h;
  367.         char *src = NULL, *dest;
  368.     int len, nbytes;
  369.     u_long was_leaf;
  370.     pgno_t oldchain;
  371.         u_char flags = 0;
  372.  
  373.     /* get two new pages for the split */
  374.     if ((left = _bt_allocpg(t)) == (BTHEADER *) NULL)
  375.         return (RET_ERROR);
  376.     left->h_pgno = ++(t->bt_npages);
  377.     if ((right = _bt_allocpg(t)) == (BTHEADER *) NULL)
  378.         return (RET_ERROR);
  379.     right->h_pgno = ++(t->bt_npages);
  380.  
  381.     /* do the split */
  382.     if (_bt_dopsplit(t, left, right) == RET_ERROR)
  383.         return (RET_ERROR);
  384.  
  385.     /* connect the new pages correctly */
  386.     right->h_prevpg = left->h_pgno;
  387.     left->h_nextpg = right->h_pgno;
  388.  
  389.     /*
  390.      *  Write the child pages out now.  We need them to remain
  391.      *  where they are until we finish updating parent pages,
  392.      *  however.
  393.      */
  394.  
  395.     if (_bt_write(t, left, NORELEASE) == RET_ERROR)
  396.         return (RET_ERROR);
  397.     if (_bt_write(t, right, NORELEASE) == RET_ERROR)
  398.         return (RET_ERROR);
  399.  
  400.     /* now change the root page into an internal page */
  401.     was_leaf = (h->h_flags & F_LEAF);
  402.     h->h_flags &= ~F_LEAF;
  403.     h->h_lower = (index_t) (((char *) (&(h->h_linp[0]))) - ((char *) h));
  404.     h->h_upper = (index_t) t->bt_psize;
  405.     (void) bzero((char *) &(h->h_linp[0]), (int) (h->h_upper - h->h_lower));
  406.  
  407.     /* put two new keys on root page */
  408.     where_h = left;
  409.     while (where_h) {
  410.         DATUM *data;
  411.         IDATUM *idata;
  412.  
  413.         if (was_leaf) {
  414.             data = (DATUM *) GETDATUM(where_h, 0);
  415.  
  416.             if (where_h == left) {
  417.                 len = 0;    /* first key in tree is null */
  418.             } else {
  419.                 if (data->d_flags & D_BIGKEY) {
  420.                     bcopy(&(data->d_bytes[0]),
  421.                           (char *) &oldchain,
  422.                           sizeof(oldchain));
  423.                     if (_bt_markchain(t, oldchain) == RET_ERROR)
  424.                         return (RET_ERROR);
  425.                     src = (char *) &oldchain;
  426.                     flags = D_BIGKEY;
  427.                 } else {
  428.                     src = (char *) &(data->d_bytes[0]);
  429.                     flags = 0;
  430.                 }
  431.                 len = data->d_ksize;
  432.             }
  433.         } else {
  434.             idata = (IDATUM *) GETDATUM(where_h, 0);
  435.             len = idata->i_size;
  436.             flags = idata->i_flags;
  437.             src = &(idata->i_bytes[0]);
  438.         }
  439.         dest = ((char *) h) + h->h_upper;
  440.         nbytes = len + (sizeof (IDATUM) - sizeof(char));
  441.         dest -= LONGALIGN(nbytes);
  442.         id = (IDATUM *) dest;
  443.         id->i_size = len;
  444.         id->i_pgno = where_h->h_pgno;
  445.         id->i_flags = flags;
  446.         if (len > 0)
  447.             (void) bcopy((char *) src, (char *) &(id->i_bytes[0]), len);
  448.         dest -= ((int) h);
  449.         h->h_linp[NEXTINDEX(h)] = (index_t) dest;
  450.         h->h_upper = (index_t) dest;
  451.         h->h_lower += sizeof(index_t);
  452.  
  453.         /* next page */
  454.         if (where_h == left)
  455.             where_h = right;
  456.         else
  457.             where_h = (BTHEADER *) NULL;
  458.     }
  459.  
  460.     if (_bt_release(t, left) == RET_ERROR)
  461.         return (RET_ERROR);
  462.     if (_bt_release(t, right) == RET_ERROR)
  463.         return (RET_ERROR);
  464.  
  465.     /*
  466.      *  That's it, split is done.  If we're doing a non-cached disk
  467.      *  btree, we can free up the pages we allocated, as they're on
  468.      *  disk, now.
  469.      */
  470.  
  471.     if (IS_A_DISK(t) && !ISCACHE(t)) {
  472.         (void) free ((char *) left);
  473.         (void) free ((char *) right);
  474.     }
  475.  
  476.     h->h_flags |= F_DIRTY;
  477.  
  478.     return (RET_SUCCESS);
  479. }
  480.  
  481. /*
  482.  *  _BT_DOPSPLIT -- Do the work of splitting a page
  483.  *
  484.  *    This routine takes two page pointers and splits the data on the
  485.  *    current page of the btree between them.
  486.  *
  487.  *    We do a lot of work here to handle duplicate keys on a page; we
  488.  *    have to place these keys carefully to guarantee that later searches
  489.  *    will find them correctly.  See comments in the code below for details.
  490.  *
  491.  *    Parameters:
  492.  *        t -- tree to split
  493.  *        left -- pointer to page to get left half of the data
  494.  *        right -- pointer to page to get right half of the data
  495.  *
  496.  *    Returns:
  497.  *        None.
  498.  */
  499.  
  500. int
  501. _bt_dopsplit(t, left, right)
  502.     BTREE_P t;
  503.     BTHEADER *left;
  504.     BTHEADER *right;
  505. {
  506.     BTHEADER *h = t->bt_curpage;
  507.     size_t psize;
  508.     char *where;
  509.     BTHEADER *where_h;
  510.     index_t where_i;
  511.     int nbytes, dsize, fixedsize, freespc;
  512.     index_t i;
  513.         index_t save_lower = 0 , save_upper = 0, save_i = 0;
  514.         index_t switch_i = 0;
  515.     char *save_key;
  516.     DATUM *d;
  517.     CURSOR *c;
  518.     index_t top;
  519.         int free_save = 0;
  520.     pgno_t chain;
  521.     int ignore;
  522.  
  523.     /*
  524.      *  Our strategy is to put half the bytes on each page.  We figure
  525.      *  out how many bytes we have total, and then move items until
  526.      *  the last item moved put at least 50% of the data on the left
  527.      *  page.
  528.      */
  529.     save_key = (char *) NULL;
  530.     psize = (int) t->bt_psize;
  531.     where = ((char *) left) + psize;
  532.     where_h = left;
  533.     where_i = 0;
  534.     nbytes = psize - (int) ((char *) &(h->h_linp[0]) - ((char *) h));
  535.     freespc = nbytes;
  536.  
  537.     top = NEXTINDEX(h);
  538.     if (h->h_flags & F_LEAF)
  539.         fixedsize = (sizeof(DATUM) - sizeof(char));
  540.     else
  541.         fixedsize = (sizeof(IDATUM) - sizeof(char));
  542.  
  543.     save_key = (char *) NULL;
  544.  
  545.     /* move data */
  546.     for (i = 0; i < top; i++) {
  547.  
  548.         /*
  549.          *  Internal and leaf pages have different layouts for
  550.          *  data items, but in both cases the first entry in the
  551.          *  data item is a size_t.
  552.          */
  553.         d = (DATUM *) GETDATUM(h,i);
  554.         if (h->h_flags & F_LEAF) {
  555.             dsize = d->d_ksize + d->d_dsize + fixedsize;
  556.         } else {
  557.             dsize = d->d_ksize + fixedsize;
  558.         }
  559.  
  560.         /*
  561.          *  If a page contains duplicate keys, we have to be
  562.          *  careful about splits.  A sequence of duplicate keys
  563.          *  may not begin in the middle of one page and end in
  564.          *  the middle of another; it must begin on a page boundary,
  565.          *  in order for searches on the internal nodes to work
  566.          *  correctly.
  567.          */
  568.         if (where_h == left) {
  569.             if (save_key == (char *) NULL) {
  570.                 if (h->h_flags & F_LEAF) {
  571.                     if (d->d_flags & D_BIGKEY) {
  572.                         free_save = TRUE;
  573.                         bcopy(&(d->d_bytes[0]),
  574.                              (char *) &chain,
  575.                              sizeof(chain));
  576.                         if (_bt_getbig(t, chain,
  577.                                    &save_key,
  578.                                    &ignore)
  579.                             == RET_ERROR)
  580.                             return (RET_ERROR);
  581.                     } else {
  582.                         free_save = FALSE;
  583.                         save_key = (char *) &(d->d_bytes[0]);
  584.                     }
  585.                 } else {
  586.                     IDATUM *id = (IDATUM *) d;
  587.  
  588.                     if (id->i_flags & D_BIGKEY) {
  589.                         free_save = TRUE;
  590.                         bcopy(&(id->i_bytes[0]),
  591.                              (char *) &chain,
  592.                              sizeof(chain));
  593.                         if (_bt_getbig(t, chain,
  594.                                    &save_key,
  595.                                    &ignore)
  596.                             == RET_ERROR)
  597.                             return (RET_ERROR);
  598.                     } else {
  599.                         free_save = FALSE;
  600.                         save_key = (char *)
  601.                             &(id->i_bytes[0]);
  602.                     }
  603.                 }
  604.                 save_i = 0;
  605.                 save_lower = where_h->h_lower;
  606.                 save_upper = where_h->h_upper;
  607.             } else {
  608.                 if (_bt_cmp(t, save_key, i) != 0) {
  609.                     save_lower = where_h->h_lower;
  610.                     save_upper = where_h->h_upper;
  611.                     save_i = i;
  612.                 }
  613.                 if (h->h_flags & F_LEAF) {
  614.                     if (free_save)
  615.                         (void) free(save_key);
  616.                     if (d->d_flags & D_BIGKEY) {
  617.                         free_save = TRUE;
  618.                         bcopy(&(d->d_bytes[0]),
  619.                              (char *) &chain,
  620.                              sizeof(chain));
  621.                         if (_bt_getbig(t, chain,
  622.                                    &save_key,
  623.                                    &ignore)
  624.                             == RET_ERROR)
  625.                             return (RET_ERROR);
  626.                     } else {
  627.                         free_save = FALSE;
  628.                         save_key = (char *) &(d->d_bytes[0]);
  629.                     }
  630.                 } else {
  631.                     IDATUM *id = (IDATUM *) d;
  632.  
  633.                     if (id->i_flags & D_BIGKEY) {
  634.                         free_save = TRUE;
  635.                         bcopy(&(id->i_bytes[0]),
  636.                              (char *) &chain,
  637.                              sizeof(chain));
  638.                         if (_bt_getbig(t, chain,
  639.                                    &save_key,
  640.                                    &ignore)
  641.                             == RET_ERROR)
  642.                             return (RET_ERROR);
  643.                     } else {
  644.                         free_save = FALSE;
  645.                         save_key = (char *)
  646.                             &(id->i_bytes[0]);
  647.                     }
  648.                 }
  649.             }
  650.         }
  651.  
  652.         /* copy data and update page state */
  653.         where -= LONGALIGN(dsize);
  654.         (void) bcopy((char *) d, (char *) where, dsize);
  655.         where_h->h_upper = where_h->h_linp[where_i] =
  656.             (index_t) (where - (int) where_h);
  657.         where_h->h_lower += sizeof(index_t);
  658.         where_i++;
  659.  
  660.         /* if we've moved half, switch to the right-hand page */
  661.         nbytes -= LONGALIGN(dsize) + sizeof(index_t);
  662.         if ((freespc - nbytes) > nbytes) {
  663.             nbytes = 2 * freespc;
  664.  
  665.             /* identical keys go on the same page */
  666.             if (save_i > 0) {
  667.                 /* i gets incremented at loop bottom... */
  668.                 i = save_i - 1;
  669.                 where_h->h_lower = save_lower;
  670.                 where_h->h_upper = save_upper;
  671.             }
  672.             where = ((char *) right) + psize;
  673.             where_h = right;
  674.             switch_i = where_i;
  675.             where_i = 0;
  676.         }
  677.     }
  678.  
  679.     /*
  680.      *  If there was an active scan on the database, and we just
  681.      *  split the page that the cursor was on, we may need to
  682.      *  adjust the cursor to point to the same entry as before the
  683.      *  split.
  684.      */
  685.  
  686.     c = &(t->bt_cursor);
  687.     if ((t->bt_flags & BTF_SEQINIT)
  688.         && (c->c_pgno == h->h_pgno)
  689.         && (c->c_index >= switch_i)) {
  690.         c->c_pgno = where_h->h_pgno;
  691.         c->c_index -= where_i;
  692.     }
  693.     return (RET_SUCCESS);
  694. }
  695.